#include<stdlib.h>
#include"vertexOrders.h"

int computeExantideg(const long i, const int * antidegree, const int k);

// vertices can be numbered and ordered arbitrarily
// they are identified by their indices in the vertex array

// the vertex array
long va[MAX_SIZE];


void mcrStableSort(const int nVSet, int * c) {
	// number of antineighbors
	int antidegree[MAX_SIZE];
	memset(antidegree, 0, nVSet*sizeof(int));
	// maximum number of antineighbors
	// used to complete vertex cover
	int maxantidegree = 0;
	long iu, iv;
	for (iu = 0; iu < nVSet; iu++) {
		va[iu] = iu;
		for (iv = iu+1; iv < nVSet; iv++)
			if (iu != iv && !hasEdge(iu, iv)) {
				antidegree[iu]++;
				antidegree[iv]++;
			}
		if (antidegree[iu] > maxantidegree)
			maxantidegree = antidegree[iu];
	}

	int exantideg[MAX_VALUE];
	// a negative number indicates that this parameter is not known
	memset(exantideg, -1, nVSet*sizeof(int));

	int rmin = 0;
	int nrmin = 1;
	int antidegreermin = antidegree[rmin];
	int i = nVSet - 1;
	int j;
	for (j = 1; j <= i; j++)
		if (antidegree[va[j]] < antidegreermin) {
			rmin = j;
			nrmin = 1;
			antidegreermin = antidegree[rmin];
		}
		else if (antidegree[j] == antidegreermin)
			nrmin++;

	while (i >= nrmin) {
		if (nrmin > 1)
			for (j = 0; j <= i; j++)
				if (rmin != j && antidegree[j] == antidegreermin) {
					if (exantideg[rmin] < 0)
						exantideg[rmin]=computeExantideg(rmin, antidegree, i);
					if (exantideg[j] < 0)
						exantideg[j]=computeExantideg(j, antidegree, i);
					if (exantideg[j] > exantideg[rmin]) {
						rmin = j;
						antidegreermin = antidegree[rmin];
					}
				}
	
		long aux = va[i];
		va[i] = va[rmin];
		va[rmin] = aux;
		aux = antidegree[i];
		antidegree[i] = antidegree[rmin];
		antidegree[rmin] = aux;
		aux = exantideg[i];
		exantideg[i] = exantideg[rmin];
		exantideg[rmin] = aux;
		
		for (j = 0; j < i; j++)
			if (!hasEdge(va[j], va[i])) {
				exantideg[j] -= antidegree[i];
				antidegree[j]--;
			}
			
		i--;
		rmin = 0;
		nrmin = 1;
		antidegreermin = antidegree[rmin];
		for (j = 1; j <= i; j++)
			if (antidegree[va[j]] < antidegreermin) {
				rmin = j;
				nrmin = 1;
				antidegreermin = antidegree[rmin];
			}
			else if (antidegree[j] == antidegreermin)
				nrmin++;
	}
	
	coverSort(++i, c);
	maxantidegree++;
	for (; i < nVSet; i++)
		c[i] = c[i-1] + 1 < maxantidegree ? c[i-1] + 1 : maxantidegree;
}

int computeExantideg(const long i, const int * antidegree, const int k) {
	int n = 0;
	long j;
	for (j = k; j > 0; j--)
		if (!hasEdge(i, j))
			n += antidegree[j];
	return n;
}

int coverSort(const int r, int * cover) {
	int coversize = 0;
	int i, j;

	// linking the elements of r
	int next[r+1];
	// head of the candidates list
	int head = r-1;
	for (i = r - 1; i >= 0; i--)
		next[i] = i - 1;
	// tail of the cliques list
	int tail = r;
	// head of the cliques list is r
	next[tail] = -1;

	for (i = head; i >= 0; i = head) {
		// current clique starts with size 1
		cover[i] = coversize;
		// remove i from the candidates list
		head = next[i];
		// include i in the tail of cliques list
		next[i] = next[tail];
		next[tail] = i;
		tail = i;
		
		// search for new vertices to add to the current clique
		int antj, nj;
		for (j = head, nj = next[j]; j >= 0; j = nj, nj = next[j]) {
			int cc;
			long vaj = va[j];
			for (cc = i; cc >= 0 && hasEdge(va[cc], vaj); cc = next[cc]);
			if (cc == -1) {
				cover[j] = coversize;
				// remove j from the candidates list
				if (j == head)
					head = next[j];
				else
					next[antj] = next[j];
				// include j in the tail of cliques list
				next[j] = next[tail];
				next[tail] = j;
				tail = j;
			}
			else
				antj = j;
		}
		coversize++;
	}
	// sort va array according to the list 
	long laux[r];
	for (i = next[r], j = 0; i >= 0; i = next[i], j++)
		laux[j] = va[i];
	memcpy(va, laux, r*sizeof(long));
	int iaux[r];
	for (i = next[r], j = 0; i >= 0; i = next[i], j++)
		iaux[j] = cover[i];
	memcpy(cover, iaux, r*sizeof(int));
	return coversize;
}

int indexCoverSort(const int r, int * ind, int * cover) {
	int coversz = 0;
	int i, j;

	// linking the elements of r
	int next[r+1];
	// head of the candidates list
	int head = r-1;
	for (i = r - 1; i >= 0; i--)
		next[i] = i - 1;
	// tail of the cliques list
	int tail = r;
	// head of the cliques list is r
	next[tail] = -1;

	for (i = head; i >= 0; i = head) {
		// current clique starts with size 1
		cover[i] = coversz;
		// remove i from the candidates list
		head = next[i];
		// include i in the tail of cliques list
		next[i] = next[tail];
		next[tail] = i;
		tail = i;
		
		// search for new vertices to add to the current clique
		int antj, nj;
		for (j = head, nj = next[j]; j >= 0; j = nj, nj = next[j]) {
			int cc;
			long vaindj = va[ind[j]];
			for (cc = i; cc >= 0 && hasEdge(va[ind[cc]], vaindj); cc = next[cc]);
			if (cc == -1) {
				cover[j] = coversz;
				// remove j from the candidates list
				if (j == head)
					head = next[j];
				else
					next[antj] = next[j];
				// include j in the tail of cliques list
				next[j] = next[tail];
				next[tail] = j;
				tail = j;
			}
			else
				antj = j;
		}
		coversz++;
	}
	// sort va array according to the list 
	int aux[r];
	for (i = next[r], j = 0; i >= 0; i = next[i], j++)
		aux[j] = ind[i];
	memcpy(ind, aux, r*sizeof(int));
	for (i = next[r], j = 0; i >= 0; i = next[i], j++)
		aux[j] = cover[i];
	memcpy(cover, aux, r*sizeof(int));
	return coversz;
}
